package leetcode;

import java.util.List;


public class DistinctSubsequences {
	
	public static void main(String[] args) {
		DistinctSubsequences object = new DistinctSubsequences();
		object.numDistinct2("bbbnbbnm", "nbb");
	}
	
	//Given a string S and a string T, count the number of distinct subsequences of T in S.
	//S = "rabbbit", T = "rabbit", res = 3
	
	public int numDistinct(String s, String t) {
		if (s == null || t == null || s.length() < t.length()) {
			return 0;
		}
		char[] sChas = s.toCharArray();
		char[] tChas = t.toCharArray();
		int[][] dp = new int[sChas.length][tChas.length];
		dp[0][0] = sChas[0] == tChas[0] ? 1 : 0;
		for (int i = 1; i < dp.length; i++) {
			dp[i][0] = dp[i - 1][0];
		}
		for (int i = 1; i < dp.length; i++) {
			for (int j = 0; j < dp.length; j++) {

			}
		}
		int res = 0;
		return res;
	}

	public int numDistinct2(String s, String t) {

		if (s == null || t == null || s.length() <= 0 || t.length() <= 0) {
			return 0;
		}

		// firstly, define dp[i][j] = s[0...i] contains t[0...j] subSequence
		// count;
		// just clasify with the example case rabbbit, rabb
		// while we meet rabb, rab, we get the result is 2;(C(2, 1), 2' b choose
		// 1' b)
		// and then we move i and j, then we rabbb, rabb, the res should be
		// (C(3, 2), 3' b choose 1' b)
		// while C(n, m) = C(n - 1, m) + C(n - 1, m - 1);
		// so C(n - 1, m - 1) = C(i - 1, j - 1), and C(n - 1, m) = C(i - 1, j)
		// so C(3, 2) = C(2, 1) + C(2, 2); dp[i][j] = dp[i - 1][j] +dp[i - 1][j
		// - 1]
		// above we talked is based on s[i] = s[j] ,while s[i] != s[j], dp[i][j]
		// = dp[i - 1][j]

		// also, every dp transfer is relative only dp[i - 1]
		// we can zip the memory

		int n = s.length();
		int m = t.length();
		int[] dp = new int[m];
		if (t.charAt(0) == s.charAt(0)) {
			dp[0] = 1;
		}

		for (int i = 1; i < n; i++) {
			for (int j = m - 1; j >= 1; j--) {
				if (t.charAt(j) == s.charAt(i)) {
					dp[j] = dp[j - 1] + dp[j];
				}
			}
			if (t.charAt(0) == s.charAt(i)) {
				dp[0] += 1;
			}
			for (int j = 0; j < dp.length; j++) {
				System.out.print(dp[j] + "  ");
			}
			System.out.println();
		}
		System.out.println("res: " + dp[m - 1]);
		return dp[m - 1];
	}
}
